3. LeetCode_无重复字符的最长子串

给定一个字符串s，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成

方式一:

暴力破解，通过多个循环以穷举的方式 找出答案。简单且易想到的方案，包括之前我们刷的两道算法题也可以使用暴力破解来解决，缺点就是虽然简单，但是效率非常低，并非是最优方案。

具体思路:

• 将字符串中每个字符作为一个循环，和子串的组合进行比较，从而获取最长字串长度。

如字符串abc，则第一轮比较为: 字符a和子串a、ab、abc比较，第二轮则为字符b和子串b、bc比较，以此类推，最后获取不重复的子串长度。

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int maxLength = 0;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (!judgeCharacterExist(i, j, s)) {
                    maxLength = Math.max(maxLength, j - i);
                }
            }
        }
        return maxLength;
    }


    public static boolean judgeCharacterExist(int start, int end, String param) {
        HashSet<Character> hashSet = new HashSet<>();
        for (int i = start; i < end; i++) {
            if (hashSet.contains(param.charAt(i))) {
                return true;
            }
            hashSet.add(param.charAt(i));
        }

        return false;
    }
}

该方法效率低，时间福再度为O(n³)。

方法二： 滑动窗口法

滑动窗口： 是数组和字符串中一个抽象的概念，可分为滑动和窗口两个概念理解。

窗口：即表示一个范围，通常是字符串和数组从开始到结束两个索引范围中间包含的一系列元素集合。如字符串abcd，如果开始索引和结束索引分别为0、2的话，这个窗口包含的字符则为： abc。

滑动：它表示窗口的开始和结束索引是可以往某个方向移动的。
如上面的例子开始索引和结束索引分别为0、2的话，当开始索引和结束索引都往右移动一位时，它们的索引值分别为1、3，这个窗口包含的字符为：bcd。

示例：

• abcdef
• 字符串开始索引： 0
• 字符串结束索引： 5
• 开始和结束索引范围包含的字符(abcdef)就可以看作是一个窗口

思路：

• 使用一个HashSet来实现滑动窗口，用来检查重复字符
• 维护开始和结束两个索引，默认都是从0开始

• 随着循环 向右移动结束索引

  • 遇到不是重复的字符则放入窗口里
  • 遇到重复字符则向右移动开始索引

最终得到结果。

public class Solution {
    public static Integer lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int leftPoint = 0;
        int rightPoint = 0;

        Set<Character> set = new HashSet<>();

        while(leftPoint < s.length() && rightPoint < s.length()) {
            if (!set.contains(s.charAt(rightPoint))) {
                set.add(s.charAt(rightPoint++));
                maxLength = Math.max(maxLength, rightPoint - leftPoint);
            } else {
                set.remove(s.charAt(leftPoint++));
            }
        }
        return maxLength;
    }
}

滑动窗口算法的时间复杂度为O(n)，相比于暴力破解，它的效率大大提高了。

方式三:

虽然方式使用了滑动窗口时间复杂度只有O(n)，但是如果存在重复字符还需要移动开始索引，因此我们可以考虑借助之前其他算法谈到的“空间换时间”的想法，通过借助HashMap建立字符和索引映射，避免手动移动索引。

public class Solution {
    public static Integer lengthOfLongestSubstring(String s) {
        char[] charArry = s.toCharArray();

        HashMap<Character, Integer> keyMap = new HashMap<>();
        int maxLength = 0;

        int leftPoint = 0;
        for (int i = 0; i < charArry.length; i++) {
            if (keyMap.containsKey(charArry[i])) {
                // 存在重复数据则获取索引值最大的
                leftPoint = Math.max(leftPoint, keyMap.get(charArry[i]));
            }
            // 值重复就覆盖，不重复就添加
            keyMap.put(charArry[i], i + 1);
            maxLength = Math.max(maxLength, i + 1 - leftPoint);
        }
        return maxLength;
    }
}

时间复杂度为O(n)，虽然和上一种方案的时间复杂度是一样的，但是效率还是有一定的提高(思考问题时要思考是否还有其他有优质的方案，培养发散思维)。

方式四:

上面题目分析的时候就提到了要注意题目中提到的：【字符串英文字母、数字、符号和空格组成】，这些字符是可以使用ASCII表示(如字符a的ASCII值为97，想具体了解的可以百度下)，那么我们就可以建立字符与ASCII的映射关系，从而实现重复字符的排除。

public class Solution {
    public static Integer lengthOfLongestSubstring(String s) {
        int[] index = new int[128];
        int maxLength = 0;
        int length = s.length();
        int i = 0;
        for (int j = 0; j < length; j++) {
            i = Math.max(index[s.charAt(j)], i);
            index[s.charAt(j)] = j + 1;
            maxLength = Math.max(maxLength, j + 1 - i);
        }
        return maxLength;
    }
}

• 邮箱 ：[email protected]
• Good Luck!